1. Field of the Invention
This invention is related to the field of caches and, more particularly, to error checking of replacement data used with caches.
2. Description of the Related Art
Memories may generally be subject to both hard errors and soft errors. Hard errors occur when a memory storage cell or cells has failed such that the cell or cells do not actually store values any longer. Thus, a value written to the memory cell or cells may not be read from the memory cell or cells regardless of the amount of time between the write and the read or the presence/absence of other activity in or near the memory between the write and the read. Soft errors occur if the memory cell or cells have not failed, but some external event (e.g. noise from surrounding circuitry) or some natural phenomena (such as charge leakage from dynamic random access memories, or DRAMs) has changed the value stored in the memory cell or cells between the write and the read. In either case, the value read from the memory may not be the value expected in view of the preceding write.
In order to account for the possibility of error and, in some cases, recovery therefrom, various error checking and/or correction schemes have been used in the past. For example, parity checking has been used. With parity, an additional bit is stored with a value in memory. The additional bit is the exclusive-OR (or exclusive-NOR) of the bits of the value. When the value is read, the parity bit is also read and exclusive-ORed (or exclusive-NORed) with the value to detect an error. If a single bit has changed since the value and the parity bit were stored in the memory, the exclusive-OR results in a binary one and an error is detected. However, if multiple bits have changed, the changes can offset each other in the exclusive-OR and no error is detected.
Other, more elaborate error checking/correction schemes have also been used in which various overlapping subsets of the bits of a value are exclusive-ORed to produce an error checking/correction (ECC) code. Depending upon the number of bits in the ECC code as compared to the number of bits in the underlying values and further depending upon the selected overlapping subsets, enhanced error detection may be possible. Particularly, with ECC codes it may be possible not only to detect certain errors, but also to correct the data read from the memory for some errors. For example, ECC codes that allow for single bit error correction and double bit error detection are popular. However, even the ECC codes may not detect some errors (e.g. double or triple bit errors for the example above).
Cache memories may be subject to the above-mentioned errors. Cache memories generally include storage for data as well as tags identifying the address in main memory at which the cached data is stored. Furthermore, cache memories may often store replacement data used to select a cache entry for replacement when an access to the cache misses. Any of the data, tags, or replacement data may experience the above-mentioned errors.
Errors in the replacement data may impact performance. If the replacement data is in error, it is possible that one or more cache entries will never be selected for replacement (or at least will temporarily not be selected, still impacting performance). Effectively, the non-selected entries may not be used by the cache, reducing the overall effectiveness of the cache if the data currently stored therein is not being used by the device or devices served by the cache. However, the error detection schemes described above generally are not capable of detecting all possible errors in the replacement data. Furthermore, since the replacement data may frequently include relatively few bits, storing parity or ECC bits corresponding to the replacement data alone may be inefficient. Frequently, other data (e.g. the tags) may be grouped with the replacement data and error detection data (e.g. ECC or parity) may be calculated for the group as a whole. For example, one or two parity bits might be used to cover the tags and the replacement data of a set in a set associative cache. Thus, detection of errors in the replacement data may be hampered by the occurrence of errors in the other data within the group.